//给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的
//根节点的引用。
//
// 一般来说，删除节点可分为两个步骤：
//
//
// 首先找到需要删除的节点；
// 如果找到了，删除它。
//
//
//
//
// 示例 1:
//
//
//
//
//输入：root = [5,3,6,2,4,null,7], key = 3
//输出：[5,4,6,2,null,null,7]
//解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
//一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
//另一个正确答案是 [5,2,6,null,4,null,7]。
//
//
//
//
// 示例 2:
//
//
//输入: root = [5,3,6,2,4,null,7], key = 0
//输出: [5,3,6,2,4,null,7]
//解释: 二叉树不包含值为 0 的节点
//
//
// 示例 3:
//
//
//输入: root = [], key = 0
//输出: []
//
//
//
// 提示:
//
//
// 节点数的范围 [0, 10⁴].
// -10⁵ <= Node.val <= 10⁵
// 节点值唯一
// root 是合法的二叉搜索树
// -10⁵ <= key <= 10⁵
//
//
//
//
// 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
// Related Topics 树 二叉搜索树 二叉树 👍 704 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Map;
import java.util.TreeMap;

class DeleteNodeInABst {
    public static void main(String[] args) {
        Solution solution = new DeleteNodeInABst().new Solution();
        DeleteNodeInABst.TreeNode treeNode = new DeleteNodeInABst().new TreeNode(0, null, null);
//        solution.deleteNode(treeNode, 0);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        /**
         * 递归法
         *
         * @param root
         * @param key
         * @return
         */
        public TreeNode deleteNode(TreeNode root, int key) {
            // 情况一：此时没找到删除的节点
            if (root == null) {
                return root;
            }

            // 找到节点
            if (root.val == key) {
                // 情况二：左右孩子都为空，直接删除节点，返回null即可
                // 情况三：被删除的左节点没有孩子，右节点有孩子，将右节点返回
                if (root.left == null && root.right != null) return root.right;

                    // 情况四：被删除的右节点没有孩子，左节点有孩子，将左节点返回
                else if (root.left != null && root.right == null) return root.left;

                    // 情况五：左右孩子都有节点，将左孩子放到右孩子的最左边节点，再返回右孩子
                else {
                    // 找到右孩子的最左边的节点
                    TreeNode cur = root.right;
                    while (cur.left != null) {
                        cur = cur.left;
                    }

                    // 将左孩子赋给最左边孩子的左孩子
                    cur.left = root.left;
                    //                    TreeNode temp = root;
                    //                    root = root.right;
                    return root.right;
                }
            }

            // 递归调用
            if (root.val > key) {
                root.left = deleteNode(root.left, key);
            }

            if (root.val < key) {
                root.left = deleteNode(root.right, key);
            }

            return root;
        }

        /**
         * 迭代法
         *
         * @param root
         * @param key
         * @return
         */
        /*public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) {
                return root;
            }

            TreeNode pre = null;    // 记录cur的父节点
            TreeNode cur = root;

            while (cur != null) {
                if (cur.val == key) {
                    break;
                }

                pre = cur;

                if (cur.val > key) {
                    cur = cur.left;
                } else {
                    cur = cur.right;
                }

                if (pre == null) {  // 此时只有一个节点
                    return this.deleteNodeOperation(cur);
                }

                if (pre.left != null && pre.left.val == key) {  // pre用来判断删除左孩子还是右孩子
                    pre.left = this.deleteNodeOperation(cur);
                }

                if (pre.right != null && pre.right.val == key) {  // pre用来判断删除左孩子还是右孩子
                    pre.right = this.deleteNodeOperation(cur);
                }
            }

            return root;
        }

        */

        /**
         * 用来删除节点的方法
         *
         * @return
         */
        /*public TreeNode deleteNodeOperation(TreeNode target) {
                if (target == null) return target;
                if (target.left == null) return target.right;
                if (target.right == null) return target.left;

                TreeNode cur = target.right;
                while (cur.left != null) {
                    cur = cur.left;
                }

                cur.left = target.left;
                return target.right;
         }*/

    }
//leetcode submit region end(Prohibit modification and deletion)

}
